package demo.practice.leetcode_eveyday;

import demo.practice.ListNode;

public class P86 {

    public static void main(String[] args) {
        ListNode root= new ListNode(1);
        root.next= new ListNode(4);
        root.next.next=new ListNode(3);
        root.next.next.next= new ListNode(2);
        root.next.next.next.next= new ListNode(5);
        root.next.next.next.next.next= new ListNode(2);

        P86 p86= new P86();
        p86.partition(root,3);
        
    }

    public ListNode partition(ListNode head, int x) {

        ListNode befor= new ListNode(0);
        ListNode beforhead=befor;
        ListNode behind= new ListNode(0);
        ListNode behindHead=behind;

        while (head!=null){
            if(head.val<x){
                befor.next= new ListNode(head.val);
                befor=befor.next;
            }else{
                behind.next= new ListNode(head.val);
                behind=behind.next;
            }
            head=head.next;
        }

        befor.next=behindHead.next;
        return beforhead.next;


    }
}
